/*
* leetcode 673. 最长递增子序列的个数
*
给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
注意 这个数列必须是 严格 递增的。

示例 1:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
* */
/*

* */
import java.util.*;

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n=nums.length,max=1,ans=1;
        int[] len=new int[n],count=new int[n];
        for(int i=0;i<n;i++)len[i]=count[i]=1;
        for(int i=1;i<n;i++){
            for(int j=i-1;j>=0;j--){
                if(nums[i]>nums[j]){
                    if(len[j]+1>len[i]){
                        len[i]=len[j]+1;
                        count[i]=count[j];
                    }else if(len[j]+1==len[i]){
                        count[i]+=count[j];
                    }
                }
            }
            if(len[i]>max){
                max=len[i];
                ans=count[i];
            }else if(len[i]==max){
                ans+=count[i];
            }
        }
        return ans;
    }
}